package 寒假刷题;

class NumArray {
    //树状数组
    int[] tree;
    int lowbit(int x) {
        return x & -x;
    }
    // 查询前缀和的方法
    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tree[i];
        return ans;
    }
    // 在树状数组 x 位置中增加值 u
    void add(int x, int u) {
        for (int i = x; i <= n; i += lowbit(i)) tree[i] += u;
    }
    int[] ans;
    int n;
    public NumArray(int[] nums) {
       ans = nums;
       n = nums.length;
       tree = new int[n+1];
        for (int i = 0; i < n; i++) {
            add(i+1,nums[i]);
        }
    }
    public void update(int index, int val) {
        add(index + 1, val - ans[index]);
        ans[index] = val;
    }
    public int sumRange(int left, int right) {
        return query(right + 1) - query(left);
    }
}
